﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0183_WidthOfBinaryTree : IAlgorithm
    {
        // 662. 二叉树最大宽度

        // 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
        // 树的 最大宽度 是所有层中最大的 宽度 。
        // 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
        // 题目数据保证答案将会在  32 位 带符号整数范围内。

        // 提示：
        //  树中节点的数目范围是[1, 3000]
        //  -100 <= Node.val <= 100

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public int WidthOfBinaryTree(TreeNode root)
        {
            int res = 1;
            IList<Tuple<TreeNode, int>> arr = new List<Tuple<TreeNode, int>>();
            arr.Add(new Tuple<TreeNode, int>(root, 1));
            while (arr.Count > 0)
            {
                IList<Tuple<TreeNode, int>> tmp = new List<Tuple<TreeNode, int>>();
                foreach (Tuple<TreeNode, int> pair in arr)
                {
                    TreeNode node = pair.Item1;
                    int index = pair.Item2;
                    if (node.left != null)
                    {
                        tmp.Add(new Tuple<TreeNode, int>(node.left, index * 2));
                    }
                    if (node.right != null)
                    {
                        tmp.Add(new Tuple<TreeNode, int>(node.right, index * 2 + 1));
                    }
                }
                res = Math.Max(res, arr[arr.Count - 1].Item2 - arr[0].Item2 + 1);
                arr = tmp;
            }
            return res;
        }
    }
}
